package com.cb2.algorithm.leetcode;

/**
 * <a href="https://leetcode.cn/problems/odd-even-linked-list">奇偶链表(Odd Even Linked List)</a>
 * <p>给定单链表的头节点 head ，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。</p>
 * <p>第一个节点的索引被认为是 奇数 ， 第二个节点的索引为 偶数 ，以此类推。</p>
 * <p>请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。</p>
 * <p>你必须在 O(1) 的额外空间复杂度和 O(n) 的时间复杂度下解决这个问题。</p>
 * <p>
 * <b>示例：</b>
 * <pre>
 * 示例 1:
 *      输入: head = [1,2,3,4,5]
 *      输出: [1,3,5,2,4]
 *
 * 示例 2：
 *      输入: head = [2,1,3,5,6,4,7]
 *      输出: [2,3,6,7,1,5,4]
 * </pre>
 * </p>
 * <p>
 * <b>提示:</b>
 * <ul>
 *      <li>n ==  链表中的节点数</li>
 *      <li>0 <= n <= 10^4</li>
 *      <li>-10^6 <= Node.val <= 10^6</li>
 * </ul>
 * </p>
 *
 * @author c2b
 * @since 2023/5/4 16:15
 */
public class LC0328OddEvenList_M {
    static class Solution {
        public ListNode oddEvenList(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }
            ListNode odd = head;
            ListNode evenHead = head.next;
            ListNode even = evenHead;
            while (even != null && even.next != null) {
                odd.next = even.next;
                odd = odd.next;
                even.next = odd.next;
                even = even.next;
            }
            odd.next = evenHead;
            return head;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        Printer.printListNode(solution.oddEvenList(Generator.create(1, 2, 3, 4, 5)));
        Printer.printListNode(solution.oddEvenList(Generator.create(2, 1, 3, 5, 6, 4, 7)));
    }
}